package com.zlk.algorithm.dataStructure.linkList03;

import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName FindMid
 * @description: 查找中点位置
 * @author: slfang
 * @create: 2024-01-31 17:07
 * @Version 1.0
 **/
public class FindMid {

    // 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
    // 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
    // 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
    // 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个

    @Test
    public void test(){
        SimpleNode test = null;
        test = new SimpleNode(0);
        test.next = new SimpleNode(1);
        test.next.next = new SimpleNode(2);
        test.next.next.next = new SimpleNode(3);
        test.next.next.next.next = new SimpleNode(4);
        test.next.next.next.next.next = new SimpleNode(5);
        test.next.next.next.next.next.next = new SimpleNode(6);
        test.next.next.next.next.next.next.next = new SimpleNode(7);
        test.next.next.next.next.next.next.next.next = new SimpleNode(8);
        //test.next.next.next.next.next.next.next.next.next = new SimpleNode(9);
        System.out.println(getMidNode1(test).value);
        System.out.println(midOrDownMidNode(test).value);
        System.out.println(getMidNode3(test).value);

    }

    // 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
    private SimpleNode getMidNode4(SimpleNode node){
        SimpleNode slowNode = node;
        SimpleNode fastNode = node;
        SimpleNode fatherNode = null;
        //  1  2  3  4  5  6
        while (fastNode!=null&&fastNode.next!=null){
            fastNode = fastNode.next.next;
            fatherNode = slowNode;
            slowNode = slowNode.next;
        }
        return fatherNode;
    }


    // 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
    private SimpleNode getMidNode3(SimpleNode node) {
        SimpleNode slowNode = node;
        SimpleNode fastNode = node;
        SimpleNode fatherNode = null;
        SimpleNode ffatherNode = null;
        //  1  2  3  4  5  6
        while (fastNode!=null&&fastNode.next!=null){
            fastNode = fastNode.next.next;
            ffatherNode = fatherNode;
            fatherNode = slowNode;
            slowNode = slowNode.next;
        }
        if(fastNode==null){//偶数
            return ffatherNode;
        }else{//奇数
            return fatherNode;
        }

    }


    //输入链表头节点，奇数长度返回中点，偶数长度返回下中点
    public  SimpleNode midOrDownMidNode(SimpleNode head) {
        if(head==null||head.next==null){
            if(head.next.next==null){
                return head.next;
            }else{
                return head;
            }
        }
        SimpleNode slow = head.next;
        SimpleNode fast = head.next.next;
        while (fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast.next!=null){
            return slow.next;

        }else{
            return slow;
        }
    }

    /**
     * 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
     * @param node
     */
    /**
     * 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
     *
     * 1 2 3 4 5 6 7 8 9 10
     *   s f
     *     s   f
     *       s     f
     *          s      f
     */
    private SimpleNode getMidNode1(SimpleNode head) {
        if(head==null||head.next==null||head.next.next==null){
            return head;
        }
        SimpleNode slow = head.next;
        SimpleNode fast = head.next.next;
        while (fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


}
